package leetcode.problems;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * _0411 Majority Element
 * 移除元素
 * Created by gmwang on 2018/3/23
 */
public class _0411MajorityElement {
    /**
     *   Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
         You may assume that the array is non-empty and the majority element always exist in the array.

         给定一个大小为n的数组，查找多数元素。多数元素是指出现超过n/2(n为数组长度)次。
         您可以假设数组是非空的，多数元素总是存在于数组中。
         比如：输入：[2,2]  输出：2
               输入：[4,5,4]   输出：4
     */
    /**
     * 思路：
     * 1.
     *
     * @param
     * @return
     */
    public static int majorityElement(int[] nums) {
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0 ;i< nums.length;i ++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for(Map.Entry<Integer, Integer> entry:entries){
            if(entry.getValue() > nums.length/2) sum+=entry.getKey();
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] nums = {4,5,4};
        System.out.println(majorityElement(nums));
    }
}
